/*
题目说明：
　　要求采用链表形式，求两个一元多项式的乘积：h3 = h1*h2。函数原型为：void multiplication( NODE * h1, NODE * h2, NODE * h3 )。

输入：
　　输入数据为两行，分别表示两个一元多项式。每个一元多项式以指数递增的顺序输入多项式各项的系数（整数）、指数（整数）。

　　例如：1+2x+x^2表示为：<1,0>,<2,1>,<1,2>,

输出：
　　以指数递增的顺序输出乘积： <系数,指数>,<系数,指数>,<系数,指数>,

　　零多项式的输出格式为：<0,0>,

说明：本题目有预设代码，只要提交你编写的函数即可。
*/

/*
测试用例1:
输入：
<1,0>,<2,1>,<1,2>,↵
<1,0>,<1,1>,↵
输出：
<1,0>,<3,1>,<3,2>,<1,3>,↵

测试用例2:
输入：
<0,0>,↵
<1,20>,<-8,40>,↵
输出：
<0,0>,↵

测试用例3:
输入：
<1,20>,<-8,40>,↵
<0,0>,↵
输出：
<0,0>,↵

测试用例4:
输入：
<-1,0>,<1,1>,↵
<1,0>,<1,1>,↵
输出：
<-1,0>,<1,2>,↵

测试用例5:
输入：
<5,0>,<10,1>,↵
<2,0>,<3,1>,<4,2>,<5,3>,↵
输出：
<10,0>,<35,1>,<50,2>,<65,3>,<50,4>,↵
*/

// 预设代码
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */  
 
#include <stdio.h>
#include <stdlib.h>

// 节点
typedef struct node
{
    int    coef, exp;
    struct node  *next;
} NODE;


void multiplication( NODE *, NODE * , NODE * );
void input( NODE * );
void output( NODE * );

// 将输入转换成链表
void input( NODE * head )
{
    int flag, sign, sum, x;  
    char c;
    NODE * p = head;
    
    // 循环读取输入
    while ( (c=getchar()) !='\n' )
    {
        if ( c == '<' )
        {
            sum = 0; // 输入可能不是个位数
            sign = 1; // 判断正负号
            flag = 1; // 判断输入的是系数、指数
        }
        else if ( c =='-' )
            sign = -1;
        else if( c >='0'&& c <='9' )  
        {
            sum = sum*10 + c - '0';  
        }
        else if ( c == ',' )
        { 
            if ( flag == 1 )
            {
                x = sign * sum;
                sum = 0;
                flag = 2;
                sign = 1;
            }
        }
        else if ( c == '>' )
        {
            p->next = ( NODE * ) malloc( sizeof(NODE) );
            
            // 系数
            p->next->coef = x;
            
            // 指数
            p->next->exp  = sign * sum;
            p = p->next;
            p->next = NULL;
            flag = 0;
        }
    }
}

// 将链表信息打印
void output( NODE * head )
{
    while ( head->next != NULL )
    {
        head = head->next;
        printf("<%d,%d>,", head->coef, head->exp );
    }
    printf("\n");
}

// 根据序号查找节点，序号从零开始
NODE * find_create_node(NODE * head, int ind)
{
    NODE * p = head;
    for (int i=0; i<=ind; i++)
    {
        if (p->next == nullptr)
        {
            NODE * new_node = new NODE;
            new_node->next = p->next;
            new_node->exp = i;
            p->next = new_node;
        }
      
        p = p->next;
    }
    return p;
}

// 一元多项式相乘
void multiplication( NODE * head1, NODE * head2, NODE * head3)
{
    NODE * p1 = head1->next;
    NODE * p2 = head2->next;
    
    int coef1, coef2, coef3;
    int exp1, exp2, exp3;
    
    while (p1 != nullptr)
    {
        coef1 = p1->coef;
        exp1 = p1->exp;
        
        while (p2 != nullptr)
        {
            coef2 = p2->coef;
            exp2 = p2->exp;
            
            coef3 = coef1 * coef2;
            exp3 = exp1 + exp2;
            
            // 找到要更新值的节点，如果没有，就创建
            NODE * node = find_create_node(head3, exp3);
            node->coef = node->coef + coef3;
            
            p2 = p2->next;
        }
        p1 = p1->next;
        p2 = head2->next;
    }
    
    // 删除系数为0的节点
    bool isZero = true;
    
    NODE * p3 = head3;
    while (p3->next != nullptr)
    {
        coef3 = p3->next->coef;
        if (coef3 == 0)
        {
            NODE * temp = p3->next;
            p3->next = temp->next;
            delete temp;
            continue;
        }
        p3 = p3->next;
    }
    
    // 如果节点系数都为0
    if (p3 == head3)
        head3->next = new NODE;
}

int main()
{
    NODE * head1, * head2, * head3;
  
    head1 = ( NODE * ) malloc( sizeof(NODE) );
    input( head1 );
  
    head2 = ( NODE * ) malloc( sizeof(NODE) );  
    input( head2 );
  
    head3 = ( NODE * ) malloc( sizeof(NODE) );  
    head3->next = NULL;  
    
    // 一元多项式相乘
    multiplication( head1, head2, head3 );  
    
    // 输出
    output( head3 );
    return 0;
}
  
/* PRESET CODE END - NEVER TOUCH CODE ABOVE */  